/LMAR=0/XLINE=4/FONT#0=BASL30/FONT#1=BASB30/FONT#5=ASI30[LSP,JRA]/FONT#2=ASI30[LSP,JRA]/FONT#3=SUB/FONT#4=SET1/FONT#6=GRK30/FONT#7=SUP/FONT#8=SPEC[LSP,JRA]/FONT#9=BUCK75/FONT#10=GRFX25[LSP,JRA]/FONT#11=METSB/FONT#12=NGB30/FONT#13=GERM35/FONT#14=MG[LSP,JRA]/FONT#15=GRFX35
␈↓ α←␈↓␈↓␈↓ 	DPreface     i␈↓








␈↓"β␈↓ α←␈↓␈↓	Preface␈↓












␈↓"β␈↓ α←␈↓¬␈↓ β'"...␈α∩it␈α⊃is␈α∩important␈α⊃not␈α∩to␈α⊃lose␈α∩sight␈α⊃of␈α∩the␈α⊃fact␈α∩that␈α⊃there␈α∩is␈α⊃a
␈↓ α←␈↓¬␈↓ β'difference␈αbetween␈αtraining␈αand␈αeducation.␈α If␈αcomputer␈αscience␈αis␈α
a
␈↓ α←␈↓¬␈↓ β'fundamental␈α∃discipline,␈α∃then␈α∃university␈α∃education␈α∃in␈α∃this␈α∀field
␈↓ α←␈↓¬␈↓ β'should␈α∀emphasize␈α∪enduring␈α∀fundamental␈α∪principles␈α∀rather␈α∪than
␈↓ α←␈↓¬␈↓ β'transient current technology."

␈↓"β␈↓ α←␈↓␈↓ β'␈↓ ∧zPeter Wegner, ␈↓αThree Computer Cultures␈↓ [Weg 70]         


␈↓"λ␈↓ α←␈↓This␈α⊃text␈α⊃is␈α⊃nominally␈α⊃about␈α∩LISP␈α⊃and␈α⊃data␈α⊃structures.␈α⊃However,␈α∩in␈α⊃the
␈↓ α←␈↓process␈α∞it␈α
covers␈α∞much␈α
broader␈α∞areas␈α
of␈α∞computer␈α
science.␈α∞ The␈α∞author␈α
has
␈↓ α←␈↓long␈α
felt␈α∞that␈α
the␈α∞beginning␈α
student␈α
of␈α∞computer␈α
science␈α∞has␈α
been␈α∞getting␈α
a
␈↓ α←␈↓distorted␈α
and␈α
disjointed␈α
picture␈α
of␈α
the␈α
field.␈α
In␈α
some␈α
ways␈α
this␈α∞confusion␈α
is
␈↓ α←␈↓natural;␈α∪the␈α∪field␈α∀has␈α∪been␈α∪growing␈α∀at␈α∪such␈α∪a␈α∀rapid␈α∪rate␈α∪that␈α∀few␈α∪are
␈↓ α←␈↓prepared␈α∂to␈α∂be␈α⊂judged␈α∂experts␈α∂in␈α∂all␈α⊂areas␈α∂of␈α∂the␈α∂discipline.␈α⊂ The␈α∂current
␈↓ α←␈↓alternative␈α∞seems␈α∞to␈α∂be␈α∞to␈α∞give␈α∞a␈α∂few␈α∞introductory␈α∞courses␈α∂in␈α∞programming
␈↓ α←␈↓and␈α
machine␈α
organization␈α
followed␈αby␈α
relatively␈α
specialized␈α
courses␈α
in␈αmore
␈↓ α←␈↓technical␈α∀areas.␈α∀The␈α∀difficulty␈α∀with␈α∀this␈α∀approach␈α∀is␈α∀that␈α∀much␈α∀of␈α∪the
␈↓ α←␈↓technical␈α≤material␈α≠never␈α≤gets␈α≤related.␈α≠The␈α≤student's␈α≤perspective␈α≠and
␈↓ α←␈↓motivation␈α
suffer␈α
in␈α
the␈α
process.␈α
This␈α
book␈α
uses␈α
LISP␈α
as␈α
a␈α
means␈α
for␈α
relating
␈↓ α←␈↓topics␈α
which␈α
normally␈α
get␈α
treated␈α
in␈α
several␈α
separate␈α
courses.␈α
The␈α
point␈α
is␈α
not
␈↓ α←␈↓that␈α
we␈α
␈↓¬can␈↓␈α
do␈α
this␈α
in␈α
LISP,␈α
but␈α
rather␈α
that␈α
it␈α
is␈α
␈↓¬natural␈↓␈α
to␈α
do␈α
it␈α
in␈α
LISP.
␈↓ α←␈↓The␈α∃high-level␈α∃notation␈α∃for␈α∃algorithms␈α∃is␈α∃beneficial␈α∃in␈α⊗explaining␈α∃and
␈↓ α←␈↓␈↓ii  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓understanding␈α
complex␈α
algorithms.␈α
 The␈αuse␈α
of␈α
abstract␈α
data␈α
structures␈αand
␈↓ α←␈↓abstract␈α⊃LISP␈α⊃programs␈α⊂shows␈α⊃the␈α⊃intent␈α⊂of␈α⊃structured␈α⊃programming␈α⊂and
␈↓ α←␈↓step-wise␈α
refinement.␈α
Much␈α
of␈α
the␈α
current␈α
work␈α
in␈α
mathematical␈α
theories␈α
of
␈↓ α←␈↓computation␈αis␈αbased␈αon␈αLISP-like␈αlanguages.␈αThus␈αLISP␈αis␈αa␈αformalism␈αfor
␈↓ α←␈↓describing␈α∂algorithms,␈α∂for␈α∂writing␈α∂programs,␈α∂and␈α∂for␈α∂proving␈α∂properties␈α∞of
␈↓ α←␈↓algorithms.␈α∂ We␈α∂use␈α∂data␈α∂structures␈α⊂as␈α∂the␈α∂main␈α∂thread␈α∂in␈α⊂our␈α∂discussions
␈↓ α←␈↓because␈α∩a␈α∩proper␈α⊃appreciation␈α∩of␈α∩data␈α∩structures␈α⊃as␈α∩abstract␈α∩objects␈α∩is␈α⊃a
␈↓ α←␈↓necessary prerequisite to an understanding of modern computer science.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α⊂importance␈α⊂of␈α⊂abstraction␈α⊃obviously␈α⊂goes␈α⊂much␈α⊂farther␈α⊃than␈α⊂its
␈↓ α←␈↓appearance␈αin␈αLISP.␈αAbstraction␈αhas␈αoften␈αbeen␈αused␈αin␈αother␈α
disciplines␈αas
␈↓ α←␈↓a␈αmeans␈αfor␈αcontrolling␈αcomplexity.␈α
In␈αmathematics,␈αwe␈αfrequently␈αare␈αable␈α
to
␈↓ α←␈↓gain␈αnew␈αinsights␈αby␈αrecasting␈αa␈αparticularly␈αintransigent␈αproblem␈αin␈αa␈αmore
␈↓ α←␈↓general␈α↔setting.␈α↔ Similarly,␈α↔the␈α_intent␈α↔of␈α↔an␈α↔algorithm␈α↔expressed␈α_in␈α↔a
␈↓ α←␈↓high-level␈α∞language␈α∞like␈α∞Fortran␈α∞or␈α∞PL/1␈α∞is␈α∞more␈α∞readily␈α∞apparent␈α∞than␈α∞its
␈↓ α←␈↓machine-language␈α⊗equivalent.␈α⊗ These␈α⊗are␈α⊗both␈α⊗examples␈α⊗of␈α⊗the␈α⊗use␈α∃of
␈↓ α←␈↓abstraction.␈α∂Our␈α∞use␈α∂of␈α∂abstraction␈α∞will␈α∂impinge␈α∞on␈α∂both␈α∂the␈α∞mathematical
␈↓ α←␈↓and␈αthe␈αprogramming␈αaspects.␈α Initially,␈αwe␈αwill␈αtalk␈αabout␈αdata␈αstructures␈αas
␈↓ α←␈↓abstract␈α∩objects␈α∩just␈α∪as␈α∩the␈α∩mathematician␈α∪takes␈α∩the␈α∩natural␈α∪numbers␈α∩as
␈↓ α←␈↓abstract␈α⊂entities.␈α⊂We␈α⊂will␈α⊂attempt␈α⊂to␈α⊂categorize␈α⊂properties␈α⊂common␈α⊃to␈α⊂data
␈↓ α←␈↓structures␈α∞and␈α∞introduce␈α∞notation␈α∂for␈α∞describing␈α∞functions␈α∞defined␈α∂on␈α∞these
␈↓ α←␈↓abstractions.␈α⊂At␈α⊂this␈α⊃level␈α⊂of␈α⊂discussion␈α⊂we␈α⊃are␈α⊂thinking␈α⊂of␈α⊃our␈α⊂LISP-like
␈↓ α←␈↓language␈α
primarily␈αas␈α
a␈αnotational␈α
convenience␈αrather␈α
than␈α
a␈αcomputational
␈↓ α←␈↓device.␈α∃ However,␈α∃after␈α∃a␈α∃certain␈α∃familiarity␈α∃has␈α∃been␈α∃established␈α∃it␈α∀is
␈↓ α←␈↓important␈αto␈αlook␈αat␈αour␈αwork␈αfrom␈αthe␈αviewpoint␈αof␈αcomputer␈αscience.␈αHere
␈↓ α←␈↓we␈α⊂must␈α⊂think␈α⊂of␈α⊂the␈α⊂computational␈α⊂aspects␈α⊂of␈α⊂our␈α⊂notation.␈α⊂We␈α⊂must␈α∂be
␈↓ α←␈↓concerned␈α∩with␈α∩the␈α∩representational␈α∩problems:␈α∩implementation␈α∩on␈α∩realistic
␈↓ α←␈↓machines,␈α∀and␈α∀efficiency␈α∪of␈α∀algorithms␈α∀and␈α∪data␈α∀structures.␈α∀However,␈α∪it
␈↓ α←␈↓cannot␈αbe␈αover-emphasized␈αthat␈αour␈αneed␈αfor␈αunderstanding␈αis␈αbest␈αserved␈αat
␈↓ α←␈↓the␈α⊂higher␈α⊂level␈α⊂of␈α⊂abstraction;␈α∂the␈α⊂advantage␈α⊂of␈α⊂a␈α⊂high-level␈α⊂language␈α∂is
␈↓ α←␈↓notational␈α∩rather␈α∩than␈α∩computational.␈α∩That␈α⊃is,␈α∩it␈α∩allows␈α∩us␈α∩to␈α∩think␈α⊃and
␈↓ α←␈↓represent␈α
our␈α
algorithms␈α∞in␈α
mathematical␈α
terms␈α
rather␈α∞than␈α
in␈α
terms␈α∞of␈α
the
␈↓ α←␈↓machine.␈α It␈αis␈αafter␈αa␈αclear␈αunderstanding␈αof␈αthe␈αproblem␈αis␈αattained␈αthat␈α
we
␈↓ α←␈↓should begin thinking about representation.
␈↓"β␈↓ α←␈↓␈↓ β'We␈αcan␈αexploit␈αthe␈α
analogy␈αwith␈αtraditional␈αmathematics␈αa␈α
bit␈αfurther.
␈↓ α←␈↓When␈α⊗we␈α⊗write␈α⊗␈↓αsqrt(x)␈↓␈α⊗in␈α∃Fortran,␈α⊗for␈α⊗example,␈α⊗we␈α⊗are␈α⊗initially␈α∃only
␈↓ α←␈↓concerned␈α≤with␈α≤␈↓αsqrt␈↓␈α≤as␈α≤a␈α≤mathematical␈α≤function␈α≤defined␈α≤such␈α≠that
␈↓ α←␈↓␈↓αx = sqrt(x)*sqrt(x)␈↓.␈α∂We␈α∂are␈α∂not␈α⊂interested␈α∂in␈α∂the␈α∂specific␈α∂algorithm␈α⊂used␈α∂to
␈↓ α←␈↓approximate␈α
the␈α
function␈α∞intended␈α
in␈α
the␈α
notation.␈α∞Indeed,␈α
thought␈α
of␈α∞as␈α
a
␈↓ α←␈↓mathematical␈α⊃notation,␈α⊃it␈α⊂doesn't␈α⊃matter␈α⊃how␈α⊂␈↓αsqrt␈↓␈α⊃is␈α⊃computed.␈α⊃We␈α⊂might
␈↓ α←␈↓wish␈α
to␈α
prove␈α
some␈α
properties␈α
of␈αthe␈α
algorithm␈α
which␈α
we␈α
are␈α
encoding.␈α If␈α
so,
␈↓ α←␈↓we␈α
would␈α
only␈α∞use␈α
the␈α
mathematical␈α
properties␈α∞of␈α
the␈α
idealized␈α∞square␈α
root
␈↓ α←␈↓function.␈α
Only␈α
later,␈α
after␈α
we␈α
had␈α
convinced␈α
ourselves␈α
of␈α
the␈αcorrect␈α
encoding
␈↓ α←␈↓of␈α⊗our␈α⊗intention␈α⊗in␈α⊗the␈α↔Fortran␈α⊗program,␈α⊗would␈α⊗we␈α⊗worry␈α↔about␈α⊗the
␈↓ α←␈↓computational␈α∂aspects␈α∞of␈α∂the␈α∞Fortran␈α∂implementation␈α∞␈↓αsqrt␈↓.␈α∂The␈α∂typical␈α∞user
␈↓ α←␈↓␈↓␈↓ 	2Preface     iii␈↓

␈↓"β␈↓ α←␈↓will␈α∪never␈α∪proceed␈α∪deeper␈α∪into␈α∪the␈α∪representation␈α∪than␈α∪this;␈α∪only␈α∀if␈α∪his
␈↓ α←␈↓computation␈α≠is␈α≤lethargic␈α≠due␈α≠to␈α≤inefficiencies,␈α≠or␈α≠inaccurate␈α≤due␈α≠to
␈↓ α←␈↓uncooperative␈α∞approximations,␈α∞will␈α
he␈α∞look␈α∞at␈α
the␈α∞actual␈α∞implementation␈α
of
␈↓ α←␈↓␈↓αsqrt␈↓.
␈↓"β␈↓ α←␈↓␈↓ β'Just␈αas␈α
it␈αis␈α
unnecessary␈αto␈α
learn␈αmachine␈α
language␈αto␈α
study␈αnumerical
␈↓ α←␈↓algorithms,␈α∂it␈α∞is␈α∂also␈α∂unnecessary␈α∞to␈α∂learn␈α∞machine␈α∂language␈α∂to␈α∞understand
␈↓ α←␈↓non-numerical␈α∂or␈α∂data␈α∂structure␈α∞processes.␈α∂ We␈α∂make␈α∂a␈α∂distinction␈α∞between
␈↓ α←␈↓data␈α⊗structures␈α⊗and␈α↔storage␈α⊗structures.␈α⊗Data␈α⊗structures␈α↔are␈α⊗abstractions,
␈↓ α←␈↓independent␈αof␈α␈↓¬how␈↓␈αthey␈αare␈αimplemented␈αon␈αa␈αmachine.␈α Data␈αstructures␈αare
␈↓ α←␈↓representations␈α_of␈α↔information␈α_chosen␈α↔to␈α_exhibit␈α↔certain␈α_ordering␈α↔and
␈↓ α←␈↓accessibility␈α≤relationships␈α≤between␈α≤data␈α≤items.␈α≤ Storage␈α≤structures␈α≠are
␈↓ α←␈↓particular␈αimplementations␈αof␈αthe␈αabstract␈αideas.␈α Certainly␈αwe␈αcannot␈αignore
␈↓ α←␈↓storage␈αstructures␈αwhen␈αwe␈αare␈α
deciding␈αupon␈αthe␈αdata␈αstructures␈α
which␈αwill
␈↓ α←␈↓encode␈α⊃the␈α⊃algorithm,␈α⊃but␈α⊃the␈α⊃interesting␈α⊃aspects␈α⊃of␈α⊃the␈α∩representation␈α⊃of
␈↓ α←␈↓information␈α
can␈α∞be␈α
discussed␈α∞at␈α
the␈α∞level␈α
of␈α∞data␈α
structures␈α∞with␈α
no␈α∞loss␈α
of
␈↓ α←␈↓generality.␈α∂ The␈α∂mapping␈α∞of␈α∂data␈α∂structures␈α∞to␈α∂storage␈α∂structures␈α∂is␈α∞usually
␈↓ α←␈↓quite␈α∞machine␈α∞dependent␈α∂and␈α∞we␈α∞are␈α∞more␈α∂interested␈α∞in␈α∞ideas␈α∂than␈α∞coding
␈↓ α←␈↓tricks.␈α∞ We␈α∞will␈α∞see␈α∞that␈α∞it␈α∞is␈α∞possible,␈α∞and␈α∞most␈α∞beneficial,␈α∞to␈α∞structure␈α∞our
␈↓ α←␈↓programs␈α∩such␈α∪that␈α∩there␈α∪is␈α∩a␈α∪very␈α∩clean␈α∪interface␈α∩between␈α∪the␈α∩abstract
␈↓ α←␈↓algorithm␈α⊃and␈α⊃the␈α⊃chosen␈α⊃representation.␈α⊃ That␈α⊃is,␈α⊃there␈α⊃will␈α⊃be␈α⊃a␈α⊃set␈α⊃of
␈↓ α←␈↓representation-manipulating␈α∞programs␈α∞to␈α∞test,␈α∞select␈α∞or␈α∞construct␈α∞elements␈α
of
␈↓ α←␈↓the␈αdomain;␈α
and␈αthere␈α
will␈αbe␈αa␈α
program␈αencoding␈α
the␈αalgorithm.␈αChanges␈α
of
␈↓ α←␈↓representations␈α∃only␈α∃require␈α∃changes␈α∃to␈α∃the␈α∃programs␈α∃which␈α⊗access␈α∃the
␈↓ α←␈↓representation, not to the basic program.
␈↓"β␈↓ α←␈↓␈↓ β'One␈αimportant␈αinsight␈αwhich␈αshould␈αbe␈αcultivated␈αin␈αthis␈αprocess␈αis␈αthe
␈↓ α←␈↓distinction␈α⊃between␈α⊃the␈α⊃concepts␈α⊃of␈α⊂function␈α⊃and␈α⊃algorithm.␈α⊃ The␈α⊃idea␈α⊂of
␈↓ α←␈↓function␈α∞is␈α∞mathematical␈α
and␈α∞is␈α∞independent␈α
of␈α∞any␈α∞notion␈α∞of␈α
computation;
␈↓ α←␈↓the␈α
meaning␈αof␈α
"algorithm"␈α
is␈αcomputational,␈α
the␈α
effect␈αof␈α
an␈αalgorithm␈α
being
␈↓ α←␈↓to␈α
compute␈αa␈α
function.␈α
Thus␈αthere␈α
are␈α
typically␈αmany␈α
algorithms␈α
which␈αwill
␈↓ α←␈↓compute a specific function.
␈↓"β␈↓ α←␈↓␈↓ β'This␈α⊃text␈α⊃is␈α⊃␈↓¬not␈↓␈α⊃meant␈α⊃to␈α⊃be␈α⊃a␈α⊃programming␈α⊃manual␈α⊃for␈α⊃LISP.␈α⊃ A
␈↓ α←␈↓certain␈α∞amount␈α∂of␈α∞time␈α∂is␈α∞spent␈α∂giving␈α∞insights␈α∂into␈α∞techniques␈α∂for␈α∞writing
␈↓ α←␈↓LISP␈α⊃functions.␈α⊃ There␈α⊃are␈α⊃two␈α⊃reasons␈α⊃for␈α⊃this.␈α⊃First,␈α⊃the␈α⊃style␈α⊃of␈α⊂LISP
␈↓ α←␈↓programming␈α∞is␈α∞quite␈α∞different␈α∞from␈α∞that␈α∞of␈α∞"normal"␈α∞programming.␈α
 LISP
␈↓ α←␈↓was␈α~one␈α≠of␈α~the␈α~first␈α≠languages␈α~to␈α~exploit␈α≠the␈α~virtues␈α≠of␈α~recursive
␈↓ α←␈↓programming␈αand␈αexplore␈αthe␈αpower␈αof␈αprocedure-valued␈αvariables.␈α Second,
␈↓ α←␈↓we␈α
will␈α
spend␈α
a␈α
great␈α
deal␈α
of␈α
time␈α
discussing␈α
various␈α
levels␈α
of␈α
implementation
␈↓ α←␈↓of␈α∪the␈α∪language.␈α∩LISP␈α∪is␈α∪an␈α∩excellent␈α∪medium␈α∪for␈α∪introducing␈α∩standard
␈↓ α←␈↓techniques␈αin␈αdata␈αstructure␈αmanipulation.␈αTechniques␈αfor␈αimplementation␈α
of
␈↓ α←␈↓recursion,␈α⊂implementation␈α⊂of␈α∂complex␈α⊂data␈α⊂structures,␈α⊂storage␈α∂management,
␈↓ α←␈↓and␈α∃symbol␈α⊗table␈α∃manipulation␈α⊗are␈α∃easily␈α∃motivated␈α⊗in␈α∃the␈α⊗context␈α∃of
␈↓ α←␈↓language␈α∞implementation.␈α∂Many␈α∞of␈α∂these␈α∞standard␈α∂techniques␈α∞first␈α∂arose␈α∞in
␈↓ α←␈↓the␈α∂implementation␈α∂of␈α⊂LISP.␈α∂But␈α∂it␈α∂is␈α⊂pointless␈α∂to␈α∂attempt␈α∂a␈α⊂discussion␈α∂of
␈↓ α←␈↓implementation unless the reader has a thorough grasp of the language.
␈↓ α←␈↓␈↓iv  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓␈↓ β'Granting␈αthe␈αefficacy␈αof␈αour␈αendeavor␈αin␈αabstraction,␈αwhy␈αstudy␈αLISP?
␈↓ α←␈↓LISP␈α∪is␈α∀at␈α∪least␈α∀fifteen␈α∪years␈α∪old␈α∀and␈α∪many␈α∀new␈α∪languages␈α∀have␈α∪been
␈↓ α←␈↓proposed.␈α∃ The␈α⊗difficulty␈α∃is␈α⊗that␈α∃the␈α⊗appropriate␈α∃combination␈α⊗of␈α∃these
␈↓ α←␈↓features␈α
is␈α
not␈α
present␈α
in␈α
any␈α
other␈α
language.␈α
LISP␈α
unifies␈α∞and␈α
rationalizes
␈↓ α←␈↓many␈α
divergent␈α
formulations␈α
of␈αlanguage␈α
constructs.␈α
 One␈α
might␈αsurmise␈α
that
␈↓ α←␈↓a␈α∩new␈α∪language,␈α∩profiting␈α∪from␈α∩LISP's␈α∩experience,␈α∪would␈α∩make␈α∪a␈α∩better
␈↓ α←␈↓pedagogical␈α
tool.␈α A␈α
strong␈αsuccessor␈α
has␈αnot␈α
arrived,␈αand␈α
toy␈α
languages␈αare
␈↓ α←␈↓suspect␈αfor␈αseveral␈αreasons.␈αThe␈αstudent␈αmay␈αsuspect␈αthat␈αhe␈αis␈αa␈αsubject␈αin␈α
a
␈↓ α←␈↓not␈α∪too␈α∪clever␈α∪experiment␈α∪being␈α∪performed␈α∪upon␈α∪him␈α∪by␈α∪his␈α∩instructor.
␈↓ α←␈↓Having␈α∩a␈α∪backlog␈α∩of␈α∪fifteen␈α∩years␈α∩of␈α∪experience␈α∩and␈α∪example␈α∩programs
␈↓ α←␈↓should␈αdo␈αmuch␈αto␈αalleviate␈αthis␈αdiscomfort.␈α The␈αdevelopment␈αof␈αLISP␈αalso
␈↓ α←␈↓shows␈α⊂many␈α⊂of␈α⊂the␈α⊂mistakes␈α∂that␈α⊂the␈α⊂original␈α⊂implementors␈α⊂and␈α∂designers
␈↓ α←␈↓made.␈α
 We␈α
will␈α
point␈α
out␈α
the␈α
flaws␈α
and␈α
pitfalls␈α
awaiting␈α
the␈αunwary␈α
language
␈↓ α←␈↓designer.
␈↓"β␈↓ α←␈↓␈↓ β'We␈αclaim␈α
the␈αmore␈αinteresting␈α
aspects␈αof␈αLISP␈α
for␈αstudents␈αof␈α
computer
␈↓ α←␈↓science␈αlie␈αnot␈αin␈αits␈αfeatures␈αas␈αa␈αprogramming␈αlanguage,␈αbut␈αin␈αwhat␈αit␈αcan
␈↓ α←␈↓show␈αabout␈αthe␈α␈↓¬structure␈↓␈αof␈αcomputer␈αscience.␈α There␈αis␈αa␈αrapidly␈αexpanding
␈↓ α←␈↓body␈α⊃of␈α⊃knowledge␈α⊃unique␈α⊃to␈α⊃computer␈α⊃science,␈α⊃neither␈α⊃mathematical␈α⊂nor
␈↓ α←␈↓engineering␈αper␈α
se.␈α Much␈α
of␈αthis␈αarea␈α
is␈αpresented␈α
most␈αclearly␈α
by␈αstudying
␈↓ α←␈↓LISP.
␈↓"β␈↓ α←␈↓␈↓ β'Again␈α∪there␈α∪are␈α∪two␈α∪ways␈α∪to␈α∪look␈α∪at␈α∪a␈α∪high␈α∪level␈α∪language:␈α∪as␈α∪a
␈↓ α←␈↓mathematical␈α
formalism,␈α
and␈α
as␈α
a␈α
programming␈α
language.␈α
 LISP␈α
is␈α
a␈α
better
␈↓ α←␈↓formalism␈α⊂than␈α⊂most␈α⊂of␈α⊂its␈α⊂mathematical␈α⊂rivals␈α⊂because␈α⊂there␈α⊃is␈α⊂sufficient
␈↓ α←␈↓organizational␈α
complexity␈α
present␈αin␈α
LISP␈α
so␈α
as␈αto␈α
make␈α
its␈αimplementation␈α
a
␈↓ α←␈↓realistic␈α∀computer␈α∀science␈α∀task␈α∪and␈α∀not␈α∀just␈α∀an␈α∀interesting␈α∪mathematical
␈↓ α←␈↓curiosity.␈α∪ Much␈α∪of␈α∪the␈α∪power␈α∪of␈α∩LISP␈α∪lies␈α∪in␈α∪its␈α∪simplicity.␈α∪ The␈α∩data
␈↓ α←␈↓structures␈αare␈αrich␈αenough␈αto␈αeasily␈αdescribe␈αsophisticated␈αalgorithms␈αbut␈αnot
␈↓ α←␈↓so␈α
rich␈α
as␈α
to␈α
become␈αobfuscatory.␈α
 Most␈α
every␈α
aspect␈α
of␈α
the␈αimplementation␈α
of
␈↓ α←␈↓LISP␈αand␈αits␈α
translators␈αhas␈αimmediate␈α
implications␈αto␈αthe␈αimplementation␈α
of
␈↓ α←␈↓other languages and to the design of programming languages in general.
␈↓"β␈↓ α←␈↓␈↓ β'We␈α⊃will␈α⊂describe␈α⊃language␈α⊂translators␈α⊃(interpreters␈α⊂and␈α⊃compilers)␈α⊂as
␈↓ α←␈↓LISP␈α∂functions.␈α∂ The␈α∂structure␈α∂of␈α∂these␈α∂translators␈α∂when␈α∂exposed␈α∂as␈α∂LISP
␈↓ α←␈↓functions␈α⊂aids␈α⊂immensely␈α⊂in␈α⊂understanding␈α⊂the␈α⊂essential␈α⊂character␈α⊃of␈α⊂such
␈↓ α←␈↓translators.␈α This␈αis␈αpartly␈αdue␈αto␈αthe␈αsimplicity␈αof␈αthe␈αlanguage,␈αbut␈αperhaps
␈↓ α←␈↓more␈α⊃due␈α⊂to␈α⊃our␈α⊂ability␈α⊃to␈α⊃go␈α⊂right␈α⊃to␈α⊂the␈α⊃essential␈α⊃translating␈α⊂algorithm
␈↓ α←␈↓without becoming bogged down in details of syntax.
␈↓"β␈↓ α←␈↓␈↓ β'LISP␈α∩has␈α∩very␈α∩important␈α∩implications␈α∩in␈α∩the␈α∩field␈α∩of␈α⊃programming
␈↓ α←␈↓language␈αsemantics,␈α
and␈αis␈αthe␈α
dominant␈αlanguage␈αin␈α
the␈αclosely␈αrelated␈α
study
␈↓ α←␈↓of␈αprovability␈αof␈αproperties␈αof␈αprograms.␈α The␈αidea␈αof␈αproving␈α
properties␈αof
␈↓ α←␈↓programs␈α⊗has␈α⊗been␈α⊗around␈α⊗for␈α↔a␈α⊗very␈α⊗long␈α⊗time.␈α⊗Goldstein␈α↔and␈α⊗von
␈↓ α←␈↓Neumann␈α↔were␈α↔aware␈α↔of␈α↔the␈α↔practical␈α↔benefits␈α↔of␈α↔such␈α↔endeavors.␈α↔J.
␈↓ α←␈↓McCarthy's␈α∃work␈α⊗in␈α∃LISP␈α⊗and␈α∃the␈α∃Theory␈α⊗of␈α∃Computation␈α⊗sought␈α∃to
␈↓ α←␈↓establish␈α⊂formalisms␈α⊂and␈α⊂rules␈α∂of␈α⊂inference␈α⊂for␈α⊂reasoning␈α⊂about␈α∂programs.
␈↓ α←␈↓However,␈α∂the␈α∂working␈α∂programmers␈α∞recognized␈α∂debugging␈α∂as␈α∂the␈α∂only␈α∞tool
␈↓ α←␈↓␈↓␈↓ 	<Preface     v␈↓

␈↓"β␈↓ α←␈↓with␈α which␈α to␈α generate␈α!a␈α "correct"␈α program,␈α though␈α!clearly␈α the
␈↓ α←␈↓non-occurrence␈α∂of␈α∂bugs␈α∂is␈α∂no␈α∂guarantee␈α∂of␈α∂correctness.␈α∂ Until␈α⊂very␈α∂recently
␈↓ α←␈↓techniques␈α∞for␈α
establishing␈α∞correctness␈α
of␈α∞practical␈α
programs␈α∞simply␈α∞did␈α
not
␈↓ α←␈↓exist.
␈↓"β␈↓ α←␈↓␈↓ β'A recent set of events is beginning to change this.

␈↓"λ␈↓ α←␈↓␈↓↓1.␈↓␈α
Programs␈α
are␈αbecoming␈α
so␈α
large␈αand␈α
complex␈α
that,␈αeven␈α
though␈α
we␈αwrite
␈↓ α←␈↓␈↓ β∂in␈α∂a␈α∂high-level␈α∂language,␈α∂our␈α∞intuitions␈α∂are␈α∂not␈α∂sufficient␈α∂to␈α∂sustain␈α∞us
␈↓ α←␈↓␈↓ β∂when␈α∞we␈α
try␈α∞to␈α
find␈α∞bugs.␈α
We␈α∞are␈α
literally␈α∞being␈α
forced␈α∞to␈α∞look␈α
beyond
␈↓ α←␈↓␈↓ β∂debugging.
␈↓"	␈↓ α←␈↓␈↓↓2.␈↓␈α∂The␈α∞formalisms␈α∂are␈α∂maturing.␈α∞We␈α∂know␈α∞a␈α∂lot␈α∂more␈α∞about␈α∂how␈α∂to␈α∞write
␈↓ α←␈↓␈↓ β∂"structured␈α
programs";␈α
we␈α
know␈α
how␈α
to␈α
design␈α
languages␈α
whose␈α
constructs
␈↓ α←␈↓␈↓ β∂are␈αmore␈αamenable␈αto␈αproof␈αtechniques.␈α And␈αmost␈αimportantly,␈αthe␈αtools
␈↓ α←␈↓␈↓ β∂we␈α→need␈α→for␈α→expressing␈α→properties␈α→of␈α→programs␈α→are␈α→finally␈α→being
␈↓ α←␈↓␈↓ β∂developed.
␈↓"	␈↓ α←␈↓␈↓↓3.␈↓␈α∀The␈α∀development␈α∀of␈α∀on-line␈α∪techniques.␈α∀The␈α∀on-line␈α∀system,␈α∀with␈α∪its
␈↓ α←␈↓␈↓ β∂sophisticated␈α∩display␈α∩editors,␈α∩debuggers␈α∩and␈α∩file␈α∩handlers,␈α∩is␈α∩the␈α⊃only
␈↓ α←␈↓␈↓ β∂reason␈α⊃that␈α⊃the␈α⊃traditional␈α⊃means␈α⊃of␈α⊃construction␈α⊃and␈α⊃modification␈α⊃of
␈↓ α←␈↓␈↓ β∂complex␈α∞programs␈α∞and␈α∞systems␈α∞has␈α
been␈α∞able␈α∞to␈α∞survive␈α∞this␈α∞long.␈α
The
␈↓ α←␈↓␈↓ β∂interactive␈α∪experience␈α∪can␈α∪now␈α∩be␈α∪adapted␈α∪to␈α∪program␈α∪verifiers␈α∩and
␈↓ α←␈↓␈↓ β∂synthesizers.

␈↓"β␈↓ α←␈↓␈↓ β'This␈α∪view␈α∩of␈α∪the␈α∩programming␈α∪process␈α∩blends␈α∪well␈α∩with␈α∪the␈α∩LISP
␈↓ α←␈↓philosophy.␈α
 We␈αwill␈α
show␈αthat␈α
the␈α
most␈αnatural␈α
way␈αto␈α
write␈αLISP␈α
programs
␈↓ α←␈↓is␈α"structured"␈αin␈αthe␈αbest␈αsense␈αof␈αthe␈αword,␈αbeing␈αclean␈αin␈αcontrol␈αstructure,
␈↓ α←␈↓concise␈α∞by␈α
not␈α∞attempting␈α
to␈α∞do␈α∞too␈α
much,␈α∞and␈α
independent␈α∞of␈α∞a␈α
particular
␈↓ α←␈↓data representation.
␈↓"β␈↓ α←␈↓␈↓ β'Many␈α
of␈αthe␈α
existing␈α
techniques␈αfor␈α
establishing␈α
correctness␈αoriginated
␈↓ α←␈↓in␈α⊗McCarthy's␈α⊗investigations␈α⊗of␈α⊗LISP;␈α∃and␈α⊗some␈α⊗very␈α⊗recent␈α⊗work␈α∃on
␈↓ α←␈↓mathematical␈α
models␈α
for␈α
programming␈αlanguages␈α
is␈α
easily␈α
motivated␈α
from␈αa
␈↓ α←␈↓discussion of LISP.
␈↓"β␈↓ α←␈↓␈↓ β'LISP␈αis␈αthe␈αstarting␈α
point␈αfor␈αthose␈αinterested␈αin␈α
Artificial␈αIntelligence.
␈↓ α←␈↓It␈α∃is␈α∃no␈α∃longer␈α∃the␈α∃"research"␈α∃language,␈α∃but␈α∃has␈α∃become␈α∃the␈α∃"systems"
␈↓ α←␈↓language␈αfor␈αA.I.␈αToday's␈αresearch␈αlanguages␈αare␈αbuilt␈αon␈αLISP,␈αusing␈αLISP
␈↓ α←␈↓as a machine language.
␈↓"β␈↓ α←␈↓␈↓ β'Finally␈αthere␈αare␈αcertain␈αproperties␈αof␈αLISP-like␈αlanguages␈αwhich␈αmake
␈↓ α←␈↓them␈α∩the␈α∩natural␈α∩candidate␈α∩for␈α∩interactive␈α∩program␈α∩specification.␈α∩ In␈α⊃the
␈↓ α←␈↓chapter␈α∞on␈α∞implications␈α∞of␈α∞LISP␈α∞we␈α∞will␈α∞characterize␈α∞"LISP-like"␈α∞and␈α
show
␈↓ α←␈↓how interactive methods can be developed.
␈↓"β␈↓ α←␈↓␈↓ β'This␈α⊂text␈α∂is␈α⊂primarily␈α∂designed␈α⊂for␈α∂undergraduates␈α⊂and␈α⊂therefore␈α∂an
␈↓ α←␈↓attempt␈α
is␈α∞made␈α
to␈α∞make␈α
it␈α
self-contained.␈α∞There␈α
are␈α∞basically␈α
five␈α∞areas␈α
in
␈↓ α←␈↓which␈α
to␈α
partition␈α
the␈α
topics:␈α
the␈α
mechanics␈α
of␈α
the␈α
language,␈α
the␈αevaluation
␈↓ α←␈↓of␈αexpressions␈αin␈αLISP,␈αthe␈αstatic␈αstructure␈αof␈αLISP,␈αthe␈αdynamic␈αstructure␈αof
␈↓ α←␈↓␈↓vi  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓LISP,␈α∩and␈α∩the␈α∩efficient␈α∩representation␈α∩of␈α∩data␈α∩structures␈α∪and␈α∩algorithms.
␈↓ α←␈↓Each␈α
area␈α∞builds␈α
on␈α∞the␈α
previous.␈α
Taken␈α∞as␈α
a␈α∞group␈α
these␈α∞topics␈α
introduce
␈↓ α←␈↓much of what is interesting computer science.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α
first␈αarea␈α
develops␈α
the␈αprogramming␈α
philosophy␈αof␈α
LISP:␈α
the␈αuse
␈↓ α←␈↓of␈α∂data␈α∂structures␈α∞in␈α∂programming;␈α∂the␈α∞language␈α∂primitives,␈α∂recursion,␈α∞and
␈↓ α←␈↓other␈α∞control␈α∞structures.␈α∞ The␈α∞second␈α∞area,␈α∞involving␈α∞a␈α∞careful␈α∞study␈α∞of␈α
the
␈↓ α←␈↓meaning␈α∞of␈α∞evaluation␈α∂in␈α∞LISP,␈α∞gives␈α∞insights␈α∂into␈α∞other␈α∞languages␈α∂and␈α∞to
␈↓ α←␈↓the␈α⊂general␈α⊂question␈α⊂of␈α⊃implementation.␈α⊂The␈α⊂next␈α⊂two␈α⊂areas␈α⊃are␈α⊂involved
␈↓ α←␈↓with␈α⊃implementation.␈α⊃The␈α⊃section␈α∩on␈α⊃static␈α⊃structure␈α⊃deals␈α⊃with␈α∩the␈α⊃basic
␈↓ α←␈↓organization␈α
of␈α
memory␈α
for␈α
a␈α
LISP␈α
machine -- be␈α
it␈α
hardware␈α∞or␈α
simulated
␈↓ α←␈↓in␈αsoftware.␈αThe␈αdynamics␈αof␈αLISP␈αdiscusses␈αthe␈αprimitive␈αcontrol␈αstructures
␈↓ α←␈↓necessary␈α∂for␈α∞implementation␈α∂of␈α∞the␈α∂LISP␈α∞control␈α∂structures␈α∂and␈α∞procedure
␈↓ α←␈↓calls.␈α∀LISP␈α∃compilers␈α∀are␈α∃discussed␈α∀here.␈α∀ The␈α∃final␈α∀section␈α∃relates␈α∀our
␈↓ α←␈↓discussion␈α
of␈αLISP␈α
and␈α
its␈αimplementation␈α
to␈α
the␈αmore␈α
traditional␈αmaterial␈α
of
␈↓ α←␈↓a␈α
data␈α
structures␈αcourse.␈α
We␈α
discuss␈αthe␈α
problems␈α
of␈α
efficient␈αrepresentation
␈↓ α←␈↓of␈α→data␈α→structures.␈α→By␈α→this␈α~point␈α→the␈α→student␈α→should␈α→have␈α~a␈α→better
␈↓ α←␈↓understanding␈α⊃of␈α⊂the␈α⊃uses␈α⊂of␈α⊃data␈α⊂structures␈α⊃and␈α⊂should␈α⊃be␈α⊃motivated␈α⊂to
␈↓ α←␈↓examine these issues with a better understanding.
␈↓"β␈↓ α←␈↓␈↓ β'A␈α
large␈αcollection␈α
of␈αproblems␈α
has␈αbeen␈α
included.␈αThe␈α
reader␈α
is␈αurged
␈↓ α←␈↓to␈αdo␈αas␈α
many␈αas␈αpossible.␈α
 The␈αproblems␈αare␈α
mostly␈αnon-trivial;␈αthey␈α
attempt
␈↓ α←␈↓to␈α∞be␈α∞realistic,␈α
introducing␈α∞some␈α∞new␈α
information␈α∞which␈α∞the␈α∞readers␈α
should
␈↓ α←␈↓be␈α∪able␈α∪to␈α∪discover␈α∪themselves.␈α∩There␈α∪are␈α∪also␈α∪a␈α∪few␈α∪rather␈α∩substantial
␈↓ α←␈↓projects.␈α At␈αleast␈αone␈αshould␈αbe␈αattempted.␈α There␈αis␈αa␈αsignificant␈αdifference
␈↓ α←␈↓between␈α⊂being␈α⊂able␈α⊃to␈α⊂program␈α⊂small␈α⊂problems␈α⊃and␈α⊂being␈α⊂able␈α⊃to␈α⊂handle
␈↓ α←␈↓large␈α∞projects.␈α
Small␈α∞programming␈α∞projects␈α
can␈α∞be␈α
accomplished␈α∞in␈α∞spite␈α
of
␈↓ α←␈↓any␈α⊃admonitions␈α⊃about␈α∩"good␈α⊃programming␈α⊃style".␈α∩ A␈α⊃large␈α⊃project␈α∩is␈α⊃an
␈↓ α←␈↓effective␈α∩demonstration␈α∩of␈α∪the␈α∩need␈α∩for␈α∩elegant␈α∪programming␈α∩techniques.
␈↓ α←␈↓The␈α∃text␈α∃is␈α∃large␈α∃and␈α∃covers␈α∀much␈α∃more␈α∃than␈α∃is␈α∃recommended␈α∃for␈α∀a
␈↓ α←␈↓one-semester course. A typical one semester course on data structures covers:
␈↓"∀␈↓ α←␈↓␈↓ βWChapter 1: all
␈↓"	␈↓ α←␈↓␈↓ βWChapter 2: without 2.4, 2.5, and 2.10.
␈↓"	␈↓ α←␈↓␈↓ βWChapter 3: without the mathematical aspects of 3.13
␈↓"	␈↓ α←␈↓␈↓ βWChapter 4: without 4.7, 4.8, and the mathematical aspects of 4.11
␈↓"	␈↓ α←␈↓␈↓ βWChapter 5: without 5.8, 5.19, and 5.20
␈↓"	␈↓ α←␈↓␈↓ βWChapter 6: without 6.8,  and 6.12 through 6.20
␈↓"	␈↓ α←␈↓␈↓ βWChapter 7: without 7.5, 7.6,  and 7.10 through 7.14
␈↓"	␈↓ α←␈↓␈↓ βWChapter 8 is also optional.
␈↓"∀␈↓ α←␈↓␈↓ β'If␈α∞a␈α∞good␈α∞interactive␈α∞LISP␈α
implementation␈α∞is␈α∞available,␈α∞then␈α∞the␈α
pace
␈↓ α←␈↓can␈α⊂be␈α⊂quickened␈α⊂and␈α⊂the␈α⊂projects␈α⊂enlarged.␈α⊂ However,␈α⊂if␈α⊂only␈α⊂a␈α⊂poor␈α∂or
␈↓ α←␈↓mediocre␈α⊂implementation␈α∂is␈α⊂accessible,␈α∂then␈α⊂the␈α∂course␈α⊂time␈α∂is␈α⊂better␈α∂spent
␈↓ α←␈↓without␈α∩␈↓¬any␈↓␈α∩actual␈α∩programming,␈α∩or␈α∩the␈α∩course␈α∩should␈α∩be␈α∪augmented␈α∩to
␈↓ α←␈↓include␈α∀an␈α∀implementation␈α∀laboratory.␈α∀ LISP␈α∀is␈α∀an␈α∀interactive␈α∀language;
␈↓ α←␈↓␈↓␈↓ 	*Preface     vii␈↓

␈↓"β␈↓ α←␈↓attempts␈α∞at␈α∂other␈α∞modes␈α∂of␈α∞operation␈α∞do␈α∂a␈α∞disservice␈α∂to␈α∞both␈α∂the␈α∞language
␈↓ α←␈↓and the user.
␈↓"β␈↓ α←␈↓␈↓ β'Finally␈α
a␈α
note␈αon␈α
the␈α
structure␈αof␈α
the␈α
text.␈αThe␈α
emphasis␈α
flows␈αfrom␈α
the
␈↓ α←␈↓abstract␈αto␈αthe␈αspecific,␈αbeginning␈αwith␈αa␈αdescription␈αof␈αthe␈αdomain␈α
of␈αLISP
␈↓ α←␈↓functions␈α⊃and␈α∩the␈α⊃operations␈α∩defined␈α⊃over␈α∩that␈α⊃domain,␈α∩and␈α⊃moves␈α∩to␈α⊃a
␈↓ α←␈↓discussion␈α
of␈α∞the␈α
details␈α∞of␈α
efficient␈α∞implementation␈α
of␈α∞LISP-like␈α
languages.
␈↓ α←␈↓The␈α∀practical-minded␈α∀programmer␈α∪might␈α∀be␈α∀put␈α∪off␈α∀by␈α∀the␈α∪"irrelevant"
␈↓ α←␈↓theory␈α∂and␈α⊂the␈α∂theoretical-minded␈α⊂mathematician␈α∂might␈α∂be␈α⊂put␈α∂off␈α⊂by␈α∂the
␈↓ α←␈↓"irrelevant"␈α⊂details␈α⊂of␈α⊂implementation.␈α⊂If␈α⊂you␈α⊂lie␈α⊂somewhere␈α⊂between␈α∂these
␈↓ α←␈↓two extremes, then welcome.

␈↓"β␈↓ α←␈↓␈↓ ¬V␈↓↓Acknowledgements␈↓
␈↓"∀␈↓ α←␈↓This␈αbook␈αbegan␈αinformally␈α
at␈αUCLA␈αin␈α1970␈α
as␈αan␈αalternative␈αto␈α
the␈αdata
␈↓ α←␈↓structures␈αcourse.␈αAny␈αbook␈αwhich␈αtakes␈αeight␈αyears␈αto␈αcomplete␈αmust␈αhave␈αa
␈↓ α←␈↓list␈α∩of␈α∩acknowledgements.␈α∩ Between␈α∩the␈α∩1970␈α∩manuscript␈α∩and␈α∩the␈α⊃present
␈↓ α←␈↓version␈α
stretches␈αan␈α
incredible␈α
list␈αof␈α
revisions␈α
and␈αrewritings.␈α
 That␈αtask␈α
was
␈↓ α←␈↓made␈α∩possible␈α∩only␈α∩by␈α∩the␈α∩document␈α∩preparation␈α∩system␈α∩at␈α∩the␈α⊃Stanford
␈↓ α←␈↓Artificial␈α∂Intelligence␈α∂Laboratory.␈α⊂ The␈α∂Artificial␈α∂Intelligence␈α⊂community␈α∂is
␈↓ α←␈↓still the superior developer of computer related tools.
␈↓"β␈↓ α←␈↓␈↓ β'The␈α∂final␈α∂shape␈α∂of␈α∂this␈α∂book␈α∂has␈α∂been␈α∂guided␈α∂by␈α∂many␈α∂sources,␈α∞but
␈↓ α←␈↓particularly␈α
I␈α
would␈α
like␈α
to␈α∞mention␈α
Michael␈α
Burke␈α
and␈α
the␈α
San␈α∞Jose␈α
State
␈↓ α←␈↓Mathematics␈α⊃Department,␈α⊂who␈α⊃allowed␈α⊂me␈α⊃to␈α⊂use␈α⊃my␈α⊂manuscript␈α⊃in␈α⊂their
␈↓ α←␈↓data␈α
structures␈αcourse.␈α
 To␈α
Ruth␈αDavis␈α
who␈α
read␈αand␈α
re-read␈αthe␈α
enumerable
␈↓ α←␈↓versions␈α∞of␈α∂paragraphs,␈α∞sections,␈α∂and␈α∞chapters,␈α∂trying␈α∞to␈α∂make␈α∞sense␈α∂out␈α∞of
␈↓ α←␈↓the␈αauthor␈αand␈αhis␈αmaterial;␈α
her␈αreward:␈αto␈αcopy-edit␈αthe␈α
manuscript.␈αRuth's
␈↓ α←␈↓aid␈α∂has␈α∂been␈α∂both␈α∂technical␈α⊂and␈α∂personal;␈α∂without␈α∂her␈α∂there␈α∂would␈α⊂be␈α∂no
␈↓ α←␈↓"Anatomy␈α∪of␈α∪LISP."␈α∩To␈α∪Nancy␈α∪Meller␈α∩of␈α∪the␈α∪UCLA␈α∪Computer␈α∩Science
␈↓ α←␈↓Department␈α∪for␈α∪typing␈α∀the␈α∪orginal␈α∪LISP␈α∪notes.␈α∀ To␈α∪Les␈α∪Earnest␈α∀of␈α∪the
␈↓ α←␈↓Stanford␈αA.I.␈αLabs␈αfor␈α
aid␈αbeyond␈αthe␈αcall␈αof␈α
duty.␈α To␈αPaulette␈αfor␈αtrying␈α
to
␈↓ α←␈↓understand.␈αTo␈αRichard␈αManuck␈αof␈αthe␈αStanford␈αComputer␈αScience␈αLibrary,
␈↓ α←␈↓a␈α∞most␈α∞excellent␈α∞librarian␈α∞with␈α∞an␈α∞exceptional␈α∞library.␈α∞ To␈α∞John␈α
McCarthy
␈↓ α←␈↓for␈α∞the␈α∞insight␈α∞which␈α∞led␈α∂to␈α∞LISP,␈α∞and␈α∞for␈α∞establishing␈α∞an␈α∂environment␈α∞at
␈↓ α←␈↓Stanford␈α
which␈α
is␈α
staffed␈α
so␈αadmirably␈α
and␈α
supplied␈α
with␈α
so␈α
many␈αtalented
␈↓ α←␈↓people.␈α∂ To␈α∞E,␈α∂PUB,␈α∂and␈α∞the␈α∂XGP,␈α∞for␈α∂existing.␈α∂ To␈α∞Dick␈α∂Dolan␈α∂and␈α∞the
␈↓ α←␈↓staff␈α⊂of␈α⊂the␈α⊃H.␈α⊂P.␈α⊂Journal,␈α⊂who␈α⊃both␈α⊂tolerated␈α⊂and␈α⊂sympathized␈α⊃with␈α⊂my
␈↓ α←␈↓attempts␈α∩to␈α∩transform␈α∩the␈α∩computer␈α∩generated␈α∩text␈α∩into␈α∩something␈α⊃which
␈↓ α←␈↓could be typeset.
␈↓"β␈↓ α←␈↓␈↓ β'Particular␈α∞mention␈α
must␈α∞go␈α∞to␈α
Guy␈α∞Steele␈α
and␈α∞Gianfranco␈α∞Prini.␈α
Guy
␈↓ α←␈↓reviewed␈α∞a␈α∂much␈α∞inferior␈α∞version␈α∂of␈α∞this␈α∞text.␈α∂His␈α∞insights,␈α∂comments,␈α∞and
␈↓ α←␈↓criticisms␈αwere␈αinvaluable.␈αWith␈αcomments␈αlike:␈α"that's␈αnot␈αa␈αcompromise,␈αit's
␈↓ α←␈↓a␈α
bloody␈α
surrender!",␈α
the␈α
text␈αwas␈α
bound␈α
to␈α
improve.␈α
Gianfranco,␈α
was␈αmore
␈↓ α←␈↓fortunate; he reviewed the results of Guy's scoldings.
␈↓ α←␈↓␈↓2  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓␈↓ β'Many␈α∂other␈α∂people␈α∂have␈α∂had␈α∂significant␈α∂influence␈α∂on␈α∂the␈α∂text.␈α∂I␈α∂feel
␈↓ α←␈↓fortunate␈αto␈αbe␈αable␈αto␈αacknowledge␈αthese␈αindividuals:␈αBruce␈αAnderson,␈αBob
␈↓ α←␈↓Boyer,␈α∀Michael␈α∀Clancy,␈α∀Bob␈α∀Doran,␈α∀Daniel␈α∀Friedman,␈α∃Richard␈α∀Gabriel,
␈↓ α←␈↓Michael␈α⊂Gordon,␈α⊂Patrick␈α⊂Greussay,␈α⊂Anthony␈α⊂Hearn,␈α⊂Freidrich␈α∂von Henke,
␈↓ α←␈↓Forrest␈α⊂Howard,␈α∂Bill␈α⊂McKeeman,␈α∂Peter␈α⊂Milne,␈α∂J S.␈α⊂Moore,␈α⊂Jorge␈α∂Morales,
␈↓ α←␈↓Charles␈α∃Prenner,␈α∃Steve␈α∃Russell,␈α∀Hanan␈α∃Samet,␈α∃Vic␈α∃Scheinman,␈α∀Herbert
␈↓ α←␈↓Stoyan,␈α∩Dennis␈α∩Ting,␈α∩and␈α∩Steve␈α∩Ward.␈α∩I␈α∩apologize␈α∩to␈α∩any␈α∩individuals␈α∩I
␈↓ α←␈↓neglected to mention; I must surely have forgotten someone.
␈↓"β␈↓ α←␈↓␈↓ β'Similarly␈αthere␈αare␈αtopics␈αrelated␈αto␈αLISP␈αwhich␈αI␈αhave␈αneglected.␈α The
␈↓ α←␈↓whole␈α∞area␈α∂of␈α∞Artificial␈α∂Intelligence␈α∞applications␈α∞has␈α∂been␈α∞slighted,␈α∂but␈α∞for
␈↓ α←␈↓every␈α
author␈α∞there␈α
must␈α
come␈α∞a␈α
time␈α∞when␈α
you␈α
have␈α∞to␈α
say␈α∞"Enough!"␈α
I've
␈↓ α←␈↓been␈α∞saying␈α∞that␈α∞for␈α∞several␈α∂years.␈α∞It␈α∞is␈α∞particularly␈α∞difficult␈α∞to␈α∂cease␈α∞when
␈↓ α←␈↓dealing␈αwith␈αa␈αtopic␈αas␈αdynamic␈α
as␈αLISP.␈αMany␈αsections␈αonly␈αhint␈α
at␈αdeeper
␈↓ α←␈↓problems, and surely some errors persist; but "Enough!"
␈↓"β␈↓ α←␈↓␈↓ β'As␈α⊃always,␈α⊃it␈α⊃is␈α⊃the␈α∩author's␈α⊃responsibility␈α⊃for␈α⊃the␈α⊃final␈α⊃shape␈α∩of␈α⊃a
␈↓ α←␈↓document;␈α→the␈α_substantial␈α→and␈α_textual␈α→errors,␈α_errors␈α→of␈α→omission␈α_and
␈↓ α←␈↓commission␈α∞are␈α∞all␈α∞mine.␈α
Each␈α∞of␈α∞the␈α∞reviewers␈α
objected␈α∞strongly␈α∞to␈α∞one␈α
or
␈↓ α←␈↓more␈α∪facets␈α∪of␈α∪this␈α∪book;␈α∪to␈α∀some,␈α∪it␈α∪was␈α∪too␈α∪theoretical;␈α∪for␈α∀some,␈α∪too
␈↓ α←␈↓practical.  I must have done something right.
␈↓"β␈↓ α←␈↓␈↓ β'␈↓ 	A␈↓αJohn Allen␈↓ 
␈↓ α←␈↓␈↓␈↓ 	>Preface     3␈↓











␈↓"β␈↓ α←␈↓α␈↓ ∧CTo my parents, John & Esther Allen
␈↓"β␈↓ α←␈↓α␈↓ ∧C␈↓ ¬;To my friend and wife, Ruth E. Davis
␈↓"β␈↓ α←␈↓α␈↓ ∧C␈↓ ¬;␈↓ ε3To my sons, Christopher & Geoffrey
␈↓ α←␈↓␈↓4  Preface␈↓ 
O␈↓

␈↓"β␈↓ α←␈↓␈↓ ¬i␈↓↓Production Note␈↓
␈↓"β␈↓ α←␈↓The␈αcreation,␈αrevision,␈α
and␈αstyling␈αof␈αthis␈α
document␈αwere␈αperfomed␈αusing␈α
the
␈↓ α←␈↓Document␈αProduction␈αSystem␈αat␈αStanford's␈αArtificial␈αIntelligence␈αLaboratory;
␈↓ α←␈↓the␈α
pages␈α
of␈α
this␈α
book␈α
are␈α
computer␈α
generated.␈α
 Since␈α
higher␈α
quality␈α
type␈α
was
␈↓ α←␈↓desired␈α∂and␈α∂such␈α∂technology␈α∂was␈α∞not␈α∂yet␈α∂readily␈α∂available,␈α∂an␈α∂attempt␈α∞was
␈↓ α←␈↓made␈αto␈αgenerate␈αmore␈αtraditional␈αtypeset␈αoutput.␈αThat␈αattempt␈αfinally␈αfailed.
␈↓ α←␈↓Thus␈αthe␈αproduction␈αof␈αthis␈αbook␈αis␈αa␈αuniquely␈αtwentieth␈αcentury␈αexperience:
␈↓ α←␈↓a␈α_result␈α_of␈α_a␈α→ninteenth␈α_century␈α_resistance␈α_and␈α_a␈α→twenty-first␈α_century
␈↓ α←␈↓anticipation.
␈↓ α←␈↓␈↓␈↓ 	_CONTENTS     5␈↓

␈↓"β␈↓ α←␈↓↓␈↓ ∧aT A B L E   O F   C O N T E N T S



␈↓ α←␈↓↓PREFACE␈↓ 
Ei

␈↓ α←␈↓↓CHAPTER␈↓ 	|PAGE␈↓



␈↓ α←␈↓␈↓↓INDEX␈↓ 
Ei␈↓

␈↓ α←␈↓␈↓ β'TEXT
␈↓ α←␈↓␈↓␈↓ 	KINDEX     1␈↓









␈↓"β␈↓ α←␈↓␈↓	Index␈↓